package com.sheng.leetcode.year2022.month08.day12;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author liusheng
 * @date 2022/08/12
 *
 * 1282. 用户分组
 *
 * 有 n 个人被分成数量未知的组。每个人都被标记为一个从 0 到 n - 1 的唯一ID 。
 * 给定一个整数数组 groupSizes ，其中 groupSizes[i] 是第 i 个人所在的组的大小。例如，如果 groupSizes[1] = 3 ，则第 1 个人必须位于大小为 3 的组中。
 * 返回一个组列表，使每个人 i 都在一个大小为 groupSizes[i] 的组中。
 * 每个人应该 恰好只 出现在 一个组 中，并且每个人必须在一个组中。如果有多个答案，返回其中 任何 一个。可以 保证 给定输入 至少有一个 有效的解。
 *
 * 示例 1：
 * 输入：groupSizes = [3,3,3,3,3,1,3]
 * 输出：[[5],[0,1,2],[3,4,6]]
 * 解释：
 * 第一组是 [5]，大小为 1，groupSizes[5] = 1。
 * 第二组是 [0,1,2]，大小为 3，groupSizes[0] = groupSizes[1] = groupSizes[2] = 3。
 * 第三组是 [3,4,6]，大小为 3，groupSizes[3] = groupSizes[4] = groupSizes[6] = 3。
 * 其他可能的解决方案有 [[2,1,6],[5],[0,4,3]] 和 [[5],[0,6,2],[4,3,1]]。
 *
 * 示例 2：
 * 输入：groupSizes = [2,1,3,3,3,2]
 * 输出：[[1],[0,5],[2,3,4]]
 *  
 * 提示：
 *
 * groupSizes.length == n
 * 1 <= n <= 500
 * 1 <= groupSizes[i] <= n
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/group-the-people-given-the-group-size-they-belong-to
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode1282 {

    @Test
    public void test01() {
//        int[] groupSizes = {3,3,3,3,3,1,3};
//        int[] groupSizes = {2,1,3,3,3,2};
        int[] groupSizes = {2,2,1,1,1,1,1,1};
        System.out.println(new Solution().groupThePeople(groupSizes).toString());
    }
}
class Solution {
    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        int length = groupSizes.length;
        List<List<Integer>> lists = new ArrayList<>();
        //获取数组中的最大值
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < length; i++) {
            if (max < groupSizes[i]) {
                max = groupSizes[i];
            }
        }
        //通过最大值进行分组
        for (int i = 1; i <= max; i++) {
            List<Integer> integers = new ArrayList<>();
            for (int j = 0; j < length; j++) {
                //当集合中的元素的值和i相等时
                if (groupSizes[j] == i) {
                    if (integers.size() < i) {
                        //如果集合长度小余分组指定的长度则，将值为i的元素，添加到集合中
                        integers.add(j);
                    } else {
                        //否则将集合添加到返回集合中，并将当前集合置为空
                        lists.add(integers);
                        integers = new ArrayList<>();
                        integers.add(j);
                    }
                    //添加操作完成后，判断当前元素是否为数组的最后一个元素，是则将当前集合放入返回集合中
                    if (j == length - 1) {
                        lists.add(integers);
                    }
                } else {
                    if (j == length - 1 && integers.size() > 0) {
                        lists.add(integers);
                    }
                }
            }
        }
        return lists;
    }
}
